//============================================================================
// Name        : Arvore.cpp
// Author      : Carlos Bentes
// Lista 01    - Questão 24 
//============================================================================
#include <iostream>
#include <string>
#include <sstream>
#include <list>

using namespace std;

typedef struct _arvoreT {
	int valor;
	struct _arvoreT *fDireito;
	struct _arvoreT *fEsquerdo;
};

//preenche arvore
void preenche(struct _arvoreT *p, int valor){
	if( valor < p->valor ){
		//se NULL, cria filho e adiciona valor
		if(p->fEsquerdo == NULL){
			struct _arvoreT *filho = new struct _arvoreT;
			filho->valor = valor;
			filho->fEsquerdo = NULL;
			filho->fDireito = NULL;
			p->fEsquerdo = filho;
		}else preenche(p->fEsquerdo,valor);//se nao, continua percorrendo
	}
	if( valor > p->valor){
		//se NULL, cria filho e adiciona valor
		if(p->fDireito == NULL){
			struct _arvoreT *filho = new struct _arvoreT;
			filho->valor = valor;
			filho->fEsquerdo = NULL;
			filho->fDireito = NULL;
			p->fDireito = filho;
		}else preenche(p->fDireito,valor);//se nao, continua percorrendo		
	}
}

void percorre_pre(struct _arvoreT *p){ //Pré-Ordem
	cout << "Valor: " << p->valor << endl;
	if(p->fEsquerdo != NULL) percorre_pre(p->fEsquerdo);
	if(p->fDireito != NULL) percorre_pre(p->fDireito);
}
void percorre_in(struct _arvoreT *p){
	if(p->fEsquerdo != NULL) percorre_in(p->fEsquerdo);
	cout << "Valor: " << p->valor << endl;
	if(p->fDireito != NULL) percorre_in(p->fDireito);
}
void percorre_pos(struct _arvoreT *p){
	if(p->fEsquerdo != NULL) percorre_pos(p->fEsquerdo);
	if(p->fDireito != NULL) percorre_pos(p->fDireito);
	cout << "Valor: " << p->valor << endl;
}
int conta_nivel(struct _arvoreT *p, int n){
	int t1, t2;
	t1 = 0; t2 = 0;
	n++;
	if(p->fEsquerdo != NULL) t1 = conta_nivel( p->fEsquerdo,n);
	if (p->fDireito != NULL)  t2 = conta_nivel( p->fDireito,n);
	n--;
	int maximo = n;
	if( maximo <= t1) maximo = t1;
	if( maximo <= t2) maximo = t2;
	return maximo;
}

void desaloca(struct _arvoreT *p){
	if(p->fEsquerdo != NULL) desaloca(p->fEsquerdo);
	if(p->fDireito != NULL) desaloca(p->fDireito);
	delete p;
}

int imprime_nivel(struct _arvoreT *p, int n, list<int> *niveis){
	int t1, t2;
	t1 = 0; t2 = 0;
	n++;
	if(p->fEsquerdo != NULL)  t1 = imprime_nivel( p->fEsquerdo,n, niveis);
	if (p->fDireito != NULL)  t2 = imprime_nivel( p->fDireito,n, niveis);
	n--;
	niveis[n].push_back(p->valor);
	int maximo = n;
	if( maximo <= t1) maximo = t1;
	if( maximo <= t2) maximo = t2;
	return maximo;
}

void imprime_caminhos(struct _arvoreT *p, string caminho){
	string temoCaminho;
	if(p->fEsquerdo != NULL){
		stringstream ss;
		ss << p->fEsquerdo->valor;
		temoCaminho = caminho + "->";
		temoCaminho = temoCaminho + ss.str();
		imprime_caminhos(p->fEsquerdo, temoCaminho);
	}
	if(p->fDireito != NULL){
		stringstream ss;
		ss << p->fDireito->valor;
		temoCaminho = caminho + "->";
		temoCaminho = temoCaminho + ss.str();
		imprime_caminhos(p->fDireito, temoCaminho);
	}
	
	if( (p->fDireito == NULL) && (p->fEsquerdo == NULL)) //folha
		cout << caminho << endl;
}


int main() {
	//declara arvore
	cout << "Alocando arvore... " << endl;
	struct _arvoreT *arvore = new struct _arvoreT;
	arvore->valor = 20;
	arvore->fEsquerdo = NULL;
	arvore->fDireito = NULL;
	preenche(arvore, 12);
	preenche(arvore, 8);
	preenche(arvore, 16);
	preenche(arvore, 11);
	preenche(arvore, 14);
	preenche(arvore, 28);
	preenche(arvore, 24);
	preenche(arvore, 35);
	preenche(arvore, 22);
	preenche(arvore, 26);
	//percorre
	cout << endl;
	cout << "-------------  Pre: " << endl;
	percorre_pre(arvore);
	cout << "-------------  In: " << endl;
	percorre_in(arvore);
	cout << "-------------  Pos: " << endl;
	percorre_pos(arvore);
	cout << endl;
	//calcula nivel recusrivamente, usando caminhamento pos-ordem	
	int alturaT = conta_nivel(arvore,0);
	cout << endl << "Altura: " << alturaT << endl << endl;
	//Imprime nivel
	cout << "Imprime niveis: " << endl;
	list<int> *niveis = new list<int> [alturaT+1];
	imprime_nivel(arvore,0,niveis);
	for(int i=0; i<alturaT+1; i++){
		if(!niveis[i].empty()){
			cout << "Nivel " << i << ": ";
			for(unsigned int t=0; t < niveis[i].size(); t++){
				cout << niveis[i].front() << " ";
				niveis[i].push_back(niveis[i].front()); //roda
				niveis[i].pop_front();
			}
			cout << endl;
		}
	}
	delete [] niveis;
	cout << endl << endl;
	//Imprime caminho folhas
	cout << "Caminhos para as folhas: " << endl;
	stringstream ss;
	ss << arvore->valor;
	imprime_caminhos(arvore,ss.str());
	//Desaloca Arvore
	cout << endl << "Desalocando...." << endl;
	desaloca(arvore);
	return 0;
}
